package gold.digger;

import gold.vo.ListNode;

/**
 * Created by fanzhenyu02 on 2020/2/28.
 */
public class LC234 {

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * @return:
     */
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow 指针现在指向链表中点
        //如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：
        if (fast != null)
            slow = slow.next;

        //从slow开始反转后面的链表，现在就可以开始比较回文串了：
        ListNode left = head;
        ListNode right = reverse(slow);

        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        LC234 an = new LC234();
        ListNode head = ListNode.createList("1->2->2->1");
        System.out.println(an.isPalindrome(head));
    }
}
